home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / sml_nj / 93src.lha / src / util / sortedlist.sml < prev    next >
Encoding:
Text File  |  1993-01-27  |  1.3 KB  |  57 lines
  1. (* Copyright 1989 by AT&T Bell Laboratories *)
  2. structure SortedList =
  3. struct
  4.  
  5. fun enter(new:int,l) =
  6.   let fun f [] = [new]
  7.     | f (l as h::t) = if new<h then new::l else if new>h then h::f t else l
  8.   in  f l
  9.   end
  10.  
  11. fun uniq l =
  12.     let fun loop([],acc) = acc
  13.       | loop(a::r,acc) = loop(r,enter(a,acc))
  14.     in loop(l,[])
  15.     end
  16.  
  17. fun merge(a,[]) = a
  18.   | merge([],a) = a
  19.   | merge(l as (i:int)::a, m as j::b) = 
  20.       if j<i then j::merge(l,b) else i::merge(a,if i<j then m else b)
  21.  
  22. local fun loop (a::b::rest) = loop(merge(a,b)::loop rest)
  23.         | loop l = l
  24. in fun foldmerge l = hd(loop l) handle Hd => []
  25. end
  26.  
  27. fun remove(x as (xl:int)::xr, y as yl::yr) =
  28.     if xl>yl then yl::remove(x,yr) else remove(xr,if xl<yl then y else yr)
  29.   | remove(_,y) = y
  30.  
  31. fun rmv (x : int,l) =
  32.     let fun loop nil = nil
  33.       | loop (a::b) = if x=a then b else a::loop b
  34.     in loop l
  35.     end
  36.  
  37. fun member l (e:int) =
  38.   let fun f [] = false
  39.     | f (h::t) = if h<e then f t else e=h
  40.   in  f l
  41.   end
  42.  
  43. fun intersect(nil,_) = nil
  44.   | intersect(_,nil) = nil
  45.   | intersect(l as (a:int)::b,r as c::d) =
  46.     if a=c then a::intersect(b,d)
  47.     else if a<c then intersect(b,r)
  48.     else intersect(l,d)
  49.  
  50. fun difference(nil,_) = nil
  51.   | difference(l,nil) = l
  52.   | difference(l as (a:int)::b,r as c::d) =
  53.     if a=c then difference(b,d)
  54.     else if a<c then a::difference(b,r)
  55.     else difference(l,d)    
  56. end
  57.